﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
//4.旋转数组
//https://leetcode.cn/problems/rotate-array/

//时间O(n),空间O(n)

//void rotate(int* nums, int numsSize, int k) 
//{
//	int newarr[numsSize];
//	k = k % numsSize;
//	for(int i = 0;i<numsSize;i++)
//	{
//		//(i + k) % numsSize 确保旋转后数据的下标
//		newarr[(i + k) % numsSize] = nums[i];
//	}
//
//	for (int i = 0; i < numsSize; i++)
//	{
//		nums[i] = newarr[i];
//	}
//}

//时间O(n),空间O(1)
//翻转函数
void revers(int* nums, int begin, int end)
{
	int tmp = 0;
	while (begin < end)
	{
		tmp = nums[begin];
		nums[begin] = nums[end];
		nums[end] = tmp;
		begin++;
		end--;
	}
}
//先翻转前n-k个元素，再翻转后k个元素，在把整个数组翻转；
//nums = [1, 2, 3, 4, 5, 6, 7], k = 3
//翻转前n-k个元素[4,3,2,1,5,6,7] 
//再翻转后k个元素[4,3,2,1,7,6,5]
//在把整个数组翻转[5,6,7,1,2,3,4]
void rotate(int* nums, int numsSize, int k) 
{
	//翻转前n - k个元素
	k = k % numsSize;
	revers(nums, 0, numsSize - k - 1);
	//再翻转后k个元素
	revers(nums, numsSize - k, numsSize - 1);
	//在把整个数组翻转
	revers(nums, 0, numsSize - 1);
}

int main()
{
	
	return 0;
}


